A High-Performance Algorithm for Identifying Frequent Items in Data Streams

摘要

Estimating frequencies of items over data streams is a common building blockin streaming data measurement and analysis. Misra and Gries introduced theirseminal algorithm for the problem in 1982, and the problem has since beenrevisited many times due its practicality and applicability. We describe ahighly optimized version of Misra and Gries' algorithm that is suitable fordeployment in industrial settings. Our code is made public via an open sourcelibrary called DataSketches that is already used by several companies andproduction systems. Our algorithm improves on two theoretical and practical aspects of priorwork. First, it handles weighted updates in amortized constant time, a commonrequirement in practice. Second, it uses a simple and fast method for mergingsummaries that asymptotically improves on prior work even for unweightedstreams. We describe experiments confirming that our algorithms are moreefficient than prior proposals.